Efficiently updating navigation databases is critical to modern navigation systems that use these navigation databases. In order to allow efficient updating, it is beneficial to reduce the size of update data packages that represent incremental updates for these navigation databases.